package tree;

import java.util.LinkedList;
import java.util.Queue;

class Node{

       public String val;

       public Node left;

       public Node right;

       public Node (String val){
           this.val = val;
           this.left = null;
           this.right = null;
       }
   }

   //可以通过一个根节点,直接拿到整个树
   //既可以直接用Node root来表示
   //也可以创建一个新的类,在类中持有上述的Node root

   class Tree{
       public Node root;
   }
public class Test1 {

    //通过这个方法,手动创建出一棵树
    public static Node createTree() {
        //先创建出所有的节点

        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");

        //把这些节点连接起来
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        c.left = g;
        return a;
    }


    //前序遍历
    public static void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public static void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    //后序遍历
    public static void postOrder(Node root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //层序遍历(代码最复杂,但是最好理解)
    //思路:
    //1.创建一个队列,队列元素就是Node,先把根节点入队列
    //2.循环取出队首元素,访问这个元素的值
    //3.把这个元素的左子树和右子树都分别入队列(在非空的情况下)
    //4.再回到2,进行循环

    public static void levelOrder(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    //求二叉树节点的个数
//    public static int size = 0;
//    public static int size(Node root){
//        //按照先序中序后序层序哪种遍历都可以,访问操作就是size++
//        if(root == null){
//            return 0;
//        }
////        int size = 0;//这样写是不行的,每次调用函数时,size都会被初始化为0
//        //要想解决,一个方法就是把size定义到外面,但是这种写法有一个弊端,那就是在笔试时,会有多个案列来测试
//        //第一个案例的测试是没问题的,但是第二个案例的size值在第一个案例size的基础上来加的,后面会越加越大
//        //因此也不建议使用这种方法
//        size++;
//        size(root.left);
//        size(root.right);
//        return size;
//    }

    //可以换一种思路,用这种递归思路来求
    public static int size(Node root) {
        if (root == null) {
            return 0;
        }
        int rootSize = 1;
        int leftSize = size(root.left);
        int rightSize = size(root.right);
        return rootSize + leftSize + rightSize;
    }

    //求二叉树叶子节点的个数
    public static int getLeafSize(Node root) {
        if (root == null) {
            return 0;
        }
        //判断当前根节点是不是叶子
        if (root.left == null && root.right == null) {
            return 1;
        }
        //如果根节点不是叶子,就递归的求左子树的叶子和右子树的叶子,加在一起就是叶子节点的总数了
        return getLeafSize(root.right) + getLeafSize(root.left);
    }

    //求二叉树第k层节点的个数,解题思路:
    //同样采用递归的思想,逐渐将大问题分解为小问题,
    //如果k < 1,就是非法输入
    //如果k = 1,就是求第一层节点的个数,二叉树不为空,节点个数就是1
    //如果k > 1,那就是求k层节点的个数,把问题转换为:求左子树k - 1层节点的个数 + 右子树k - 1层节点的个数
    //就这样一直向下去减小问题的规模
    public static int getLevelNodeCount(Node root, int k) {
        if (root == null || k < 1) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getLevelNodeCount(root.left, k - 1) + getLevelNodeCount(root.right, k - 1);
    }

    //求二叉树的高度,同样采用递归,逐步缩小问题规模的方法来解决

    public static int getHeight(Node root) {
        //当前树的高度:max(左子树的高度,右子树的高度) + 1
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

//        if(leftHeight > rightHeight){
//            return leftHeight + 1;
//        }else{
//            return rightHeight + 1;
//        }

//        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        //最简便的写法
        return Math.max(leftHeight, rightHeight) + 1;
    }


    //寻找值为val的元素是否存在,如果存在,返回对应的节点,否则返回null
    //这种递归不一定要把节点查找完,只要碰到符合的节点,就结束
    public static Node find(Node root, String val) {
        if (root == null) {
            return null;
        }
        if (root.val.equals(val)) {
            return root;
        }
        //如果根节点不满足,递归查找其左子树,如果左子树没有找到,再递归查找其右子树
        Node leftResult = find(root.left, val);
        if (leftResult != null) {
            return leftResult;
        }
        //查找右子树
//        Node rightResult = find(root.right,val);
//        if(rightResult != null){
//            return rightResult;
//        }
//        return null;

        //简化后这样写
        return find(root.right, val);
    }


    //判断一棵树是不是完全二叉树
    //针对这个二叉树进行层序遍历,遍历过程分为两个阶段,
    //①第一个阶段中,任意一个访问到的节点,都应该有两个子树,如果遇到没有子树的节点,
    // 或者遇到了只有左子树的节点,进入第二阶段(如果遇到了只有右子树的节点,可直接判断其不是完全二叉树)
    //②第二个阶段中,要求每个节点都必须是没有子树,一旦遇到了有子树的节点,就不是完全二叉树

    public static boolean isComplete(Node root) {
        if(root == null){
            //空树可以认为是完全二叉树
        }
        boolean isFirstStep = true;
        //判断是第一阶段，还是第二阶段
        //再针对树进行层序遍历
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            //对节点的子树进行判定
            if(isFirstStep){
                if(cur.left == null&&cur.right == null){
                    isFirstStep = false;
                    //没有子树，进入下一阶段
                }else if(cur.left!=null&&cur.right==null){
                    isFirstStep = false;
                    //只有左子树,进入第二阶段
                    queue.offer(cur.left);
                }else if(cur.left == null&& cur.right!=null){
                    //只有右子树,返回false
                    return false;
                }else{
                    //左右子树都有,继续往后遍历
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
            }else{
                //第二阶段的判定
                //要求所有的节点,必须都没有子树
                if(cur.left!=null||cur.right!=null){
                    return false;
                }
            }
        }
        return true;


    }


    public static void main(String[] args) {
//        //这种方法在笔试面试中很常见,这样写不太讲究封装
//        Node root = new Node("A");

//        //也可以表示一棵树,这种写法在工作中比较常见
//        Tree tree = new Tree();

        Node root = createTree();
//        System.out.println("先序遍历:");
//        preOrder(root);
//        System.out.println();
//        System.out.println("中序遍历:");
//        inOrder(root);
//        System.out.println();
//        System.out.println("后序遍历:");
//        postOrder(root);
//        System.out.println();
//        System.out.println("层序序遍历:");
//        levelOrder(root);
//        System.out.println();
//        System.out.println(size(root));
//        System.out.println(getLeafSize(root));
//        System.out.println(getLevelNodeCount(root,4));
//        System.out.println(getHeight(root));
        System.out.println(isComplete(root));
    }
}

